package 力扣日常刷题.木23一月.第01天301;

/**
 * @author 帅小伙
 * @date 2022/3/1
 * @description
 */
public class Demo05剪绳子需要取模 {


    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        final int MOD = 1000000007;
        int b = n % 3;
        long rem = 1, x = 3;
        for (int a = n / 3 - 1; a > 0; a /= 2) {
            if (a % 2 == 1) rem = (rem * x) % MOD;
            x = (x * x) % MOD;
        }
        if (b == 0) return (int) (rem * 3 % MOD);
        if (b == 1) return (int) (rem * 4 % MOD);
        return (int) (rem * 6 % MOD);
    }


}
